#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int left = -1;
        int right = nums.size();
        int i = 0;
        while(i<right){
            if(nums[i]==0){
                ++left;
                swap(nums,left,i);
                ++i;
            }
            else if(nums[i]==2){
                --right;
                swap(nums,right,i);
            }
            else{
                ++i;
            }
        }
    }
    void swap(vector<int>&nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
};

int main(){
    Solution S;
    vector<int> nums ={2,0,2,1,1,0};
    S.sortColors(nums);
    return 0;
}